from modules.Dijkstra import dijkstra


# 无向图，判断边是否已经写入
def link_is_exist(links, link):
    for el in links:
        if el[0] in link and el[1] in link:
            return True
    return False


# 获取边在三元表中的索引
def get_link_index(links, link):
    for index in range(len(links)):
        if links[index][0] in link and links[index][1] in link:
            return index

    return None


# 度表转三元表
def degree2link(degree_dic):
    links_result = []
    nodes_result = set()
    for key in degree_dic:
        nodes_result.add(key)
        for key2 in degree_dic[key]:
            line = [key, key2]
            if link_is_exist(links_result, line):
                continue
            link = [key, key2, degree_dic[key][key2]]
            links_result.append(link)
    return nodes_result, links_result


# 将算法结果解析为边索引
def result_resolve(end, result_dic, link_list):
    index_list = []
    for key in result_dic:
        if end == key:
            route_list = result_dic[key][1].copy()
            route_list.append(end)
            print(f"-->从源点到终点的最短路径为：{route_list}")
            for index in range(len(route_list) - 1):
                line = [route_list[index], route_list[index + 1]]
                link_index = get_link_index(link_list, line)
                index_list.append(link_index)
            break


    return index_list


# 三元表转度表
def link2degree(node_list, link_list):
    degree_dic = {}
    for el_node in node_list:
        el_dict = {}
        for el_link in link_list:
            if el_node == el_link[0]:
                el_dict[el_link[1]] = el_link[2]
            if el_node == el_link[1]:
                el_dict[el_link[0]] = el_link[2]
        degree_dic[el_node] = el_dict
    return degree_dic


if __name__ == '__main__':
    degree_graph = {
        'A': {'B': 2, 'C': 9},
        'B': {'A': 2, 'D': 4, 'E': 8},
        'C': {'A': 9, 'E': 10, 'F': 3},
        'D': {'B': 4, 'E': 1, 'G': 5},
        'E': {'B': 8, 'C': 10, 'D': 1, 'F': 11, 'G': 6, 'H': 12},
        'F': {'C': 3, 'E': 11, 'H': 17},
        'G': {'D': 5, 'E': 6},
        'H': {'E': 12, 'F': 17},
    }

    nodes = [
        'v1',
        'v2',
        'v3',
        'v4',
        'v5'
    ]

    links = [
        ['v1', 'v2', 5],
        ['v1', 'v3', 1],
        ['v3', 'v4', 3],
        ['v2', 'v4', 4],
        ['v4', 'v5', 10],
        ['v3', 'v5', 12]
    ]

    print(link2degree(nodes, links))
